// Created by WXX on 2021/10/23 16:16
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {

        unordered_map<char, int> hs, ht;  // hs: 滑窗s[j, i]中各字符数量; ht: t中各字符数量
        for (auto c : t) ht[c]++;

        string res;
        int cnt = 0;  // 有效字符数量
        for (int i = 0, j = 0; i < s.size(); i++) {
            hs[s[i]]++;
            if (hs[s[i]] <= ht[s[i]]) cnt++;

            while (j < s.size() && hs[s[j]] > ht[s[j]]) hs[s[j++]]--;  // 滑窗中存在多余的字符s[j]
            if (cnt == t.size()) {
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

int main() {

    cout << Solution().minWindow("ADOBECODEBANC", "ABC") << endl;  // BANC

    return 0;
}
